package 回溯;
import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Arrays;
public class leetcode90子集Ⅱ {
	public static void main(String []args) {
		int nums[] = {1,2,2};
		System.out.println(solution(nums));
	}
		// 在78 题 子集一 的基础上 去个重  去重的 前提 是排序  首先排好序 前提
		public static List<List<Integer>> solution(int nums[]) {
			Arrays.sort(nums);
			List<List<Integer>> ans =new ArrayList<>();
			LinkedList<Integer> path = new LinkedList<>();
			if(nums.length==0) {
				return ans;
			}
			process(nums,0,ans,path);
			return ans;
			
		}
		public static void process(int nums[],int index,List<List<Integer>> ans,
				LinkedList<Integer> path) {
			ans.add(new ArrayList<>(path));
			for(int i = index;i < nums.length;i++) {
				// 去重
				if(i > index && nums[i] == nums[i-1]) {
					continue;
				}
				path.add(nums[i]);
				process(nums,i+1,ans,path);
				path.removeLast();
			}
		}
}
